package xyz.naokeziteng.leetcode;

import java.util.Arrays;

//1011题 在D天内送达包裹的能力
public class ShipWithinDDays {

    public int shipWithinDays(int[] weights, int days) {
        int l = Arrays.stream(weights).max().getAsInt();
        int r = Arrays.stream(weights).sum();
        int result = r;
        while (l <= r) {
            int w = l + (r - l) / 2;
            if (getDays(weights, w) <= days) {
                result = w;
                r = w - 1;
            } else {
                l = w + 1;
            }
        }
        return result;
    }

//    public int shipWithinDays(int[] weights, int days) {
//        // 确定二分查找左右边界
//        int left = Arrays.stream(weights).max().getAsInt(), right = Arrays.stream(weights).sum();
//        while (left < right) {
//            int mid = (left + right) / 2;
//            // need 为需要运送的天数
//            // cur 为当前这一天已经运送的包裹重量之和
//            int need = 1, cur = 0;
//            for (int weight : weights) {
//                if (cur + weight > mid) {
//                    ++need;
//                    cur = 0;
//                }
//                cur += weight;
//            }
//            if (need <= days) {
//                right = mid;
//            } else {
//                left = mid + 1;
//            }
//        }
//        return left;
//    }

    //天数
    public int getDays(int[] weights, int w) {
        int days = 0;
        int acc = 0;
        for (int weight : weights) {
            if (acc + weight == w) {
                days++;
                acc = 0;
            } else if (acc + weight < w) {
                acc += weight;
            } else {
                if (acc > 0) {
                    days++;
                }
                if (weight == w) {
                    days++;
                    acc = 0;
                } else if (weight < w) {
                    acc = weight;
                } else {
                    days += (weight + w - 1) / w;
                    acc = 0;
                }
            }
        }
        if (acc > 0) {
            days++;
        }
        return days;
    }


    public static void main(String[] args) {
        ShipWithinDDays shipWithinDDays = new ShipWithinDDays();
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int days = 10;
        System.out.println(shipWithinDDays.shipWithinDays(arr, days));
        //System.out.println(shipWithinDDays.getDays(arr, 10));
//        System.out.println(shipWithinDDays.getDays(arr, 8));
    }
}
